package newBee.class1;

/**
 * https://leetcode.cn/problems/maximum-width-ramp/
 * 最大宽度坡
 * arr:[6, 0, 8, 2, 1, 5]
 * 解释：
 * 1.数组值 0-2=4，0-1=3，0-5=4，是三个坡的长度，找到最大的坡是4，
 * 2.0和8虽然不是坡，但并不影响0-2是坡
 *
 * 解题思路：
 * 1.正向遍历小压大，将所有可以当坡底的数字入栈
 * 2.反向遍历，将大于栈顶的值下标取出来，计算最大坡的距离
 */
public class Code06_maxWidthRamp {
    public static void main(String[] args) {
        int[] arr = {9, 8, 1, 0, 1, 9, 4, 0, 4, 1};
        int ans = maxWidthRamp(arr);
        System.out.println("ans = " + ans);

    }

    public static int maxWidthRamp(int[] arr) {
        int r = 0, n = arr.length, ans = 0;
        int[] stack = new int[n];

        // 从左往后遍历，找到可以最坡底的值
        for (int i = 0; i < n; i++) {
            // arr[stack[r - 1]] >= arr[i]：当栈顶 >= 下一个值时，可以做栈底，入栈
            if (r == 0 || arr[stack[r - 1]] >= arr[i]) {
                stack[r++] = i;
            }
        }
        // 从右往左遍历
        for (int i = n - 1; i >= 0; i--) {
            // 当右边的值大于栈顶时，计算坡的距离
            while (r > 0 && arr[stack[r - 1]] <= arr[i]) {
                ans = Math.max(ans, i - stack[--r]); // 计算最大坡度值
            }
        }
        return ans;
    }
}
